Data communicated and transferred digitally from one unit to another unit in a data system, may become lost or corrupted. Data error detection methods and systems are used to attempt to automatically detect errors in the received data. Some error detection methods utilize checksum including checksum based on addition and checksums based on cyclic redundancy check (CRC) techniques, both of which are discussed by way of example in a series of three articles by Barr, M., “Embedded Systems”, 12/1999 pp37-43, 1/2000 pp 37-43, and 5/2000 pp 59-70.
Both checksum and CRC techniques involve calculating and generating a “checkword” at the unit transmitting a string of data. The transmitted checkword is representative of the data sent and is appended to the string of data sent by the unit transmitting the data. On reception of the data string, a second checkword is calculated at the receiving unit performing the same calculations conducted at the transmitting unit based on the data string actually received. The second checkword is then compared with the actual transmitted checkword received. If the two checkwords match, then the probability of data loss or corruption during transmission is low, and the data string is regarded correct. If on comparison the second checkword differs from the transmitted checkword, an indication that the data string sent has been corrupted during transmission is recognized. In such cases the receiving unit may for example request to have the data resent, correct the data, or ignore the data and wait to receive additional data from a transmitting unit.
A typical checksum generates the checkword based on a sum of bytes approach, which involves purely addition functions, the sum of data taken over a unit at a time. The checksum approach is commonly used because it is relatively easy to implement, and can be executed relatively quickly. However, there are problems associated with these type of checksums. A problem arises if there are simple faults in the received data sequence, for example, the order of the data in the data sequence is changed during transmission, the checkword and checksum is unchanged. Another problem with these checksums arises if the entire data sequence or string received at the receiving unit was of all zeros. In both conditions, the first checkword calculated at the transmitting unit would match the second checkword calculated at the receiving unit using the checksum based on the sum of bytes approach, and the corruption in the data sequence would go unnoticed.
Another error detection approach mentioned above is CRC, which generates the checkword by calculating and updating the checkword and checksum on every bit of the data string, as opposed to the unit of time approach on the checksum based on addition approach. The CRC approach ensures that the simple faults and the all zeros problems are detected. However, calculating a bit at a time is much slower process than the simple checksum approach, and requires greater processor time to calculate, especially where the calculations are done 16 or 32 bits at a time.
Therefore, there is a need in the art for an encoder and method of encoding for detection of errors and corruption of data during transmission that provides a faster solution than CRC and improved fault tolerance than checksum based on addition.